P4056 [JSOI2009]火星藏宝图
这道题很容易想到O(n2)O(n^2)的暴力做法,但仔细思考一下,可以发现对于每一列的可转移的岛,行数大的一定比行数小的更优.

不妨假设这两个岛的坐标为(x1,y),(x2,y)(x1<x2≤x)(x_1,y),(x_2,y)(x_1 < x_2 \le x),当前的岛的坐标为(x,y)(x,y)

∵(x1−x2)2+(x2−x)2−(x1−x)2\because (x_1-x_2)^2+(x_2-x)^2 - (x_1-x)^2

=2x22−2x1x2−2xx2+2xx1=2(x2−x1)(x2−x)<0=2x_2^2-2x_1x_2-2xx_2+2xx_1=2(x_2-x_1)(x_2-x)<0

∴(x1−x2)2+(x2−x)2<(x1−x)2\therefore (x_1-x_2)^2+(x_2-x)^2 < (x_1-x)^2

即选择经过第二个岛的花费一定小于不选择经过第二个岛

那么我们就可以再开一个数组把每一列可以转移的岛的最大行数用数组st[k]st[k]存下来

对于状态转移方程,我们不妨假设当前岛的坐标为(i,j),定义状态fi,jf_{i,j}为走到(i,j)(i,j)的最小花费,那么只需要用O(m3)O(m^3)枚举横坐标k即可求出答案

观察转移方程fi,j=fst[k],k+(i−st[k])2+(j−k)2+wi,jf_{i,j}=f_{st[k],k}+(i-st[k])^2+(j-k)^2+w_{i,j}

为了式子更简便不妨设disk=(i−st[k])2dis_k=(i-st[k])^2

那么稍微变一下形可得disk−k2−fst[k],k=2jk−j2+wi,j−fi,jdis_k-k^2-f_{st[k],k}=2jk-j^2+w_{i,j}-f_{i,j}

令y=disk−k2−fst[k],k,x=ky=dis_k-k^2-f_{st[k],k},x=k

得y=2jx−j2+wi,j−fi,jy=2jx-j^2+w_{i,j}-f_{i,j}

到这很明显就是用斜率优化了,维护一个下凸壳求最小值,那么就可以用O(m2)O(m^2)求出了

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define cost(i, j, k) ((i - st[k]) * (i - st[k]) + (j - k) * (j - k))
#define gety(k) (dis[k] + k * k - f[st[k]][k])
using namespace std;
const int N = 2e5 + 5;

int ld[1005][1005], st[1005], f[1005][1005], dis[1005], q[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        ld[x][y] = v;
    }
    memset(f, -0x3f, sizeof(f));
    f[1][1] = ld[1][1], st[1] = 1, ld[1][1] = 0;//初始化,将ld[1][1]=0避免重复转移
    for (int i = 1; i <= m; i++)
    {
        int front = 0, tail = 0;
        q[0] = 0;
        for (int j = 1; j <= m; j++)
            dis[j] = (st[j] != 0) * (i - st[j]) * (i - st[j]);
        for (int j = 1; j <= m; j++)
        {
            if (st[j])
            {
                while (front < tail && (gety(q[tail]) - gety(q[tail - 1])) * (j - q[tail]) 
                    >= (gety(j) - gety(q[tail])) * (q[tail] - q[tail - 1]))
                    tail--;
                q[++tail] = j;//因为每次队列都会清空,所以要将之前的重新放回队列
            }
            if (!ld[i][j])
                continue;
            while (front < tail && gety(q[front + 1]) - gety(q[front]) <= 2 * j * (q[front + 1] - q[front]))
                front++;
            int k = q[front];
            f[i][j] = f[st[k]][k] - cost(i, j, k) + ld[i][j];
            st[j] = i, dis[j] = 0;
            while (front < tail && (gety(q[tail]) - gety(q[tail - 1])) * (j - q[tail]) 
                >= (gety(j) - gety(q[tail])) * (q[tail] - q[tail - 1]))
                tail--;
            q[++tail] = j;//斜率优化
        }
    }
    printf("%d", f[m][m]);
    return 0;
}